package P1线性结构;

public class InfixCalculator {
    public static void main(String[] args) {
        String expression = "1+1+1+(1-2-2*3)*2*(3/2/(1+2*2/2)+2)*2+2*1+1+2+3";
        int result = evalute(expression);
        System.out.println(result);
        System.out.println(1+1+1+(1-2-2*3)*2*(3/2/(1+2*2/2)+2)*2+2*1+1+2+3);
    }

    private static int evalute(String expression) {
        LinkedList<Character> opStack = new LinkedList();
        LinkedList<Integer> numStack = new LinkedList();

        expression = format(expression);
        String[] tokens = expression.split(" ");
        for (String token : tokens) {
            if (token.length() != 0) {  //过滤空格
                if (token.equals("+") || token.equals("-")) {
                    //栈不为空且栈顶不为( , 则算
                    while (!opStack.isEmpty() && opStack.peek() != '(') {
                        process(numStack, opStack);
                    }
                    opStack.push(token.charAt(0));
                } else if (token.equals("*") || token.equals("/")) {
                    //栈顶不为空且栈顶为* / , 则算
                    while (!opStack.isEmpty() && (opStack.peek() == '*' || opStack.peek() == '/')) {
                        process(numStack, opStack);
                    }
                    opStack.push(token.charAt(0));
                } else if (token.equals("(")) {
                    opStack.push('(');
                } else if (token.equals(")")) {
                    while (opStack.peek() != '(') {
                        process(numStack, opStack);
                    }
                    opStack.pop();
                } else {
                    numStack.push(Integer.parseInt(token));
                }
            }
        }
        while (!opStack.isEmpty()) {
            process(numStack, opStack);
        }
        return numStack.pop();
    }

    private static void process(LinkedList<Integer> numStack, LinkedList<Character> opStack) {
        int num1 = numStack.pop();
        int num2 = numStack.pop();
        char op = opStack.pop();
        if (op == '+') {
            numStack.push(num2 + num1);
        } else if (op == '-') {
            numStack.push(num2 - num1);
        } else if (op == '*') {
            numStack.push(num2 * num1);
        } else {
            numStack.push(num2 / num1);
        }
    }

    private static String format(String expression) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
                sb.append(' ');
                sb.append(c);
                sb.append(' ');
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}